#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//class Solution {
//public:
//    vector<int>c;
//
//    vector<int>rea(vector<int>& A, int b) {
//        int tmp = 0;
//        for (size_t i = 0; i < A.size() || tmp; i++) {
//            if (i < A.size())tmp += A[i] * b;
//            c.push_back(tmp % 10);
//            tmp /= 10;
//        }
//        return c;
//    }
//    vector<int> add(vector<int>& A, vector<int>& B) {
//        vector<int>c;
//        int tmp = 0;
//        for (int i = 0; i < A.size() || i < B.size() || tmp; i++) {
//            if (i < A.size())tmp += A[i];
//            if (i < B.size())tmp += B[i];
//            c.push_back(tmp % 10);
//            tmp /= 10;
//        }
//        return c;
//    }
//    vector<int> mul(vector<int>& A, vector<int>& B) {
//        vector<int>tmp;
//        for (size_t i = 0; i < B.size(); i++) {
//            c.resize(0);
//            for (int j = 0; j < i; j++)
//                c.push_back(0);
//            rea(A, B[i]);
//            tmp = add(c, tmp);
//        }
//        return tmp;
//    }
//    string multiply(string num1, string num2) {
//        if (num1 == "0" || num2 == "0")return "0";
//        vector<int>A;
//        vector<int>B;
//        for (int i = num1.size() - 1; i >= 0; i--)A.push_back(num1[i] - '0');
//        for (int i = num2.size() - 1; i >= 0; i--)B.push_back(num2[i] - '0');
//        auto c = mul(A, B);
//        string s;
//        for (int i = c.size() - 1; i >= 0; i--)s += c[i] + '0';
//        return s;
//    }
//};
//class Solution {
//public:
//    vector<int> add(vector<int>& A, vector<int>& B) {
//        vector<int>c;
//        int tmp = 0;
//        for (int i = 0; i < A.size() || i < B.size() || tmp; i++) {
//            if (i < A.size())tmp += A[i];
//            if (i < B.size())tmp += B[i];
//            c.push_back(tmp % 10);
//            tmp /= 10;
//        }
//        return c;
//    }
//    string addStrings(string num1, string num2) {
//        vector<int> A;
//        vector<int> B;
//        for (int i = num1.size() - 1; i >= 0; i--)A.push_back(num1[i] - '0');
//        for (int i = num2.size() - 1; i >= 0; i--)B.push_back(num2[i] - '0');
//        auto c = add(A, B);
//        string s;
//        for (int i = c.size() - 1; i >= 0; i--)s += c[i] + '0';
//        return s;
//    }
//};
//class Solution {
//public:
//    void reverseString(vector<char>& s) {
//        size_t l = 0;
//        size_t r = s.size() - 1;
//        while (l < r) {
//            swap(s[l], s[r]);
//            l++;
//            r--;
//        }
//
//    }
//};
//class MinStack {
//public:
//    MinStack() {}
//
//    void push(int val) {
//        if (minst.empty())minst.push(val);
//        else if (val <= minst.top())minst.push(val);
//        st.push(val);
//    }
//
//    void pop() {
//        if (st.top() == minst.top())minst.pop();
//        st.pop();
//    }
//
//    int top() {
//        return st.top();
//    }
//
//    int getMin() {
//        return minst.top();
//    }
//    stack<int>st;
//    stack<int>minst;
//
//};
//class Solution {
//public:
//    string str[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//    void dfs(string& digits, int i, string s, vector<string>& ret) {
//        if (i == digits.size()) {
//            ret.push_back(s);
//            return;
//        }
//        string tmp = str[digits[i] - '0'];
//        for (int j = 0; j < tmp.size(); j++) {
//            dfs(digits, i + 1, s + tmp[j], ret);
//        }
//    }
//    vector<string> letterCombinations(string digits) {
//        vector<string>ret;
//        if (digits.size() == 0)return ret;
//
//        dfs(digits, 0, "", ret);
//        return ret;
//    }
//};
//class Solution {
//public:
//    bool isletter(const string& s, size_t i) {
//        if (s[i] >= 'A' && s[i] <= 'Z') {
//            return true;
//        }
//        else if (s[i] >= 'a' && s[i] <= 'z') {
//            return true;
//        }
//        else return false;
//    }
//    string reverseOnlyLetters(string s) {
//        size_t begin = 0, end = s.size() - 1;
//        while (begin < end) {
//            while (begin < end && !isletter(s, begin))begin++;
//            while (begin < end && !isletter(s, end))end--;
//            if (begin < end) {
//                swap(s[begin], s[end]);
//                begin++;
//                end--;
//            }
//
//        }
//        return s;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
//        vector<vector<int>>ret;
//        queue<TreeNode*>q;
//        if (root == nullptr)return ret;
//        q.push(root);
//        int flag = 1;
//        while (!q.empty()) {
//            int sz = q.size();
//            vector<int>path;
//            for (int i = 0; i < sz; i++) {
//                TreeNode* tmp = q.front();
//                q.pop();
//                if (tmp->left != nullptr) {
//                    q.push(tmp->left);
//                }
//                if (tmp->right != nullptr) {
//                    q.push(tmp->right);
//                }
//                path.push_back(tmp->val);
//            }
//            if (flag == 1) {
//                ret.push_back(path);
//                flag = 0;
//            }
//            else {
//                std::reverse(path.begin(), path.end());
//                ret.push_back(path);
//                flag = 1;
//            }
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> levelOrder(Node* root) {
//        vector<vector<int>>ret;
//        queue<Node*>q;
//        if (root == nullptr)return ret;
//        q.push(root);
//        while (!q.empty()) {
//            int sz = q.size();
//            vector<int>path;
//            for (int i = 0; i < sz; i++) {
//                Node* tmp = q.front();
//                q.pop();
//                for (Node* child : tmp->children) {
//                    if (child != nullptr) {
//                        q.push(child);
//                    }
//                }
//                path.push_back(tmp->val);
//            }
//            ret.push_back(path);
//        }
//        return ret;
//    }
//};
//class Solution {
//    vector<vector<int>>ret;
//    vector<int>path;
//    int k;
//public:
//    vector<vector<int>> combine(int n, int _k) {
//        k = _k;
//        dfs(1, n);
//        return ret;
//    }
//    void dfs(int left, int right) {
//        if (path.size() == k) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = left; i <= right; i++) {
//            path.push_back(i);
//            dfs(i + 1, right);
//            path.pop_back();
//        }
//    }
//};
//class Solution {
//    int left, right, size;
//    vector<string>ret;
//    string path;
//public:
//    vector<string> generateParenthesis(int n) {
//        size = n;
//        dfs();
//        return ret;
//    }
//    void dfs() {
//        if (path.size() == size * 2) {
//            ret.push_back(path);
//            return;
//        }
//        if (left < size) {
//            path.push_back('(');
//            left++;
//            dfs();
//            path.pop_back();
//            left--;
//        }
//        if (right < left) {
//            path.push_back(')');
//            right++;
//            dfs();
//            path.pop_back();
//            right--;
//        }
//
//
//    }
//};
//class Solution {
//    bool check[9];
//    vector<vector<int>>ret;
//    vector<int>path;
//public:
//    vector<vector<int>> permuteUnique(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        dfs(nums);
//        return ret;
//    }
//    void dfs(vector<int>& nums) {
//        if (path.size() == nums.size()) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = 0; i < nums.size(); i++) {
//            if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
//                path.push_back(nums[i]);
//                check[i] = true;
//                dfs(nums);
//                path.pop_back();
//                check[i] = false;
//            }
//
//
//        }
//    }
//};
//class Solution {
//    int sum;
//    int tmp;
//public:
//    int subsetXORSum(vector<int>& nums) {
//        dfs(nums, 0);
//        return sum;
//    }
//    void dfs(vector<int>& nums, int pos) {
//        sum += tmp;
//        for (int i = pos; i < nums.size(); i++) {
//            tmp ^= nums[i];
//            dfs(nums, i + 1);
//            tmp ^= nums[i];
//        }
//    }
//};
//class Solution {
//    vector<vector<int>>ret;
//    vector<int>path;
//public:
//    vector<vector<int>> subsets(vector<int>& nums) {
//        dfs(nums, 0);
//        return ret;
//    }
//    void dfs(vector<int>& nums, int pos) {
//        ret.push_back(path);
//        for (int i = pos; i < nums.size(); i++) {
//            path.push_back(nums[i]);
//            dfs(nums, i + 1);
//            path.pop_back();
//        }
//    }
//};
//class Solution {
//    vector<vector<int>>ret;
//    vector<int>path;
//    bool check[7];
//public:
//    vector<vector<int>> permute(vector<int>& nums) {
//        dfs(nums);
//        return ret;
//    }
//    void dfs(vector<int>& nums) {
//        if (path.size() == nums.size()) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = 0; i < nums.size(); i++) {
//            if (check[i] == false) {
//                path.push_back(nums[i]);
//                check[i] = true;
//                dfs(nums);
//
//                path.pop_back();
//                check[i] = false;
//
//            }
//        }
//    }
//};
//class Solution {
//public:
//    vector<string> binaryTreePaths(TreeNode* root) {
//        vector<string>nums;
//        dfs(root, nums, "");
//        return nums;
//    }
//    void dfs(TreeNode* root, vector<string>& nums, string s) {
//        if (root == nullptr)return;
//        if (root->left == nullptr && root->right == nullptr) {
//            nums.push_back(s + to_string(root->val));
//            return;
//        }
//        dfs(root->left, nums, s + to_string(root->val) + "->");
//        dfs(root->right, nums, s + to_string(root->val) + "->");
//    }
//};
//class Solution {
//public:
//    int count, ret;
//    int kthSmallest(TreeNode* root, int k) {
//        count = k;
//        dfs(root);
//        return ret;
//    }
//    void dfs(TreeNode* root) {
//        if (root == nullptr || count == 0)return;
//        dfs(root->left);
//        count--;
//        if (count == 0) {
//            ret = root->val;
//            return;
//        }
//        if (count == -1)return;
//        dfs(root->right);
//    }
//
//};
//class Solution {
//public:
//    long n = LONG_MIN;
//    bool isValidBST(TreeNode* root) {
//        if (root == nullptr)return true;
//        bool left = isValidBST(root->left);
//        if (left == false)return false;
//        bool cur = false;
//        if (n < root->val) {
//            n = root->val;
//            cur = true;
//        }
//        if (cur == false)return false;
//        bool right = isValidBST(root->right);
//        return left && right && cur;
//    }
//};
//class Solution {
//public:
//    TreeNode* pruneTree(TreeNode* root) {
//        if (root == nullptr)return nullptr;
//        root->left = pruneTree(root->left);
//        root->right = pruneTree(root->right);
//        if (root->left == nullptr && root->right == nullptr && root->val == 0) {
//            delete root;
//            root = nullptr;
//        }
//        return root;
//    }
//};
//class Solution {
//public:
//    int sumNumbers(TreeNode* root) {
//        int presum = 0;
//        return dfs(root, presum);
//    }
//    int dfs(TreeNode* root, int presum) {
//        if (root == nullptr)return 0;
//        presum = presum * 10 + root->val;
//        if (root->left == nullptr && root->right == nullptr)return presum;
//        int ret = 0;
//        ret += dfs(root->left, presum);
//        ret += dfs(root->right, presum);
//        return ret;
//    }
//};
//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (root->left == nullptr)return root->val;
//        return root->val == 2 ? evaluateTree(root->left) || evaluateTree(root->right) : evaluateTree(root->left) && evaluateTree(root->right);
//
//    }
//};
//int main() {
//	cout << endl;
//	return 0;
//}
//class Solution {
//public:
//    double myPow(double x, int n) {
//        return n < 0 ? 1.0 / dfs(x, -(long)n) : dfs(x, n);
//    }
//    double dfs(double x, long n) {
//        if (n == 0)return 1.0;
//        double tmp = dfs(x, n / 2);
//        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
//    }
//};
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr)return head;
//        ListNode* next = head->next;
//        head->next = next->next;
//        next->next = head;
//        head->next = swapPairs(head->next);
//        return next;
//    }
//};
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head) {
//        if (head == nullptr || head->next == nullptr)return head;
//        ListNode* next = head->next;
//        head->next = next->next;
//        next->next = head;
//        head->next = swapPairs(head->next);
//        return next;
//    }
//};
//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//        if (l1 == nullptr)return l2;
//        if (l2 == nullptr)return l1;
//        if (l1->val < l2->val) {
//            l1->next = mergeTwoLists(l1->next, l2);
//            return l1;
//        }
//        else {
//            l2->next = mergeTwoLists(l2->next, l1);
//            return l2;
//        }
//    }
//};
//class Solution {
//public:
//    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
//        dfs(a, b, c, a.size());
//    }
//    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n) {
//        if (n == 1) {
//            c.push_back(a.back());
//            a.pop_back();
//            return;
//        }
//        dfs(a, c, b, n - 1);
//        c.push_back(a.back());
//        a.pop_back();
//        dfs(b, a, c, n - 1);
//    }
//};
//class Solution {
//public:
//    int deleteAndEarn(vector<int>& nums) {
//        const int N = 10001;
//        int hash[N] = { 0 };
//        for (auto x : nums)hash[x] += x;
//        vector<int>f(N);
//        auto g = f;
//        for (int i = 1; i < N; i++) {
//            f[i] = g[i - 1] + hash[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[N - 1], g[N - 1]);
//    }
//};
//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        return max(steal(nums, 2, n - 2) + nums[0], steal(nums, 1, n - 1));
//    }
//    int steal(vector<int>& nums, int left, int right) {
//        if (left > right)return 0;
//        int n = nums.size();
//        vector<int>f(n);
//        auto g = f;
//        f[left] = nums[left];
//        for (int i = left + 1; i <= right; i++) {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[right], g[right]);
//    }
//};
//class Solution {
//public:
//    int massage(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 0)return 0;
//        vector<int>f(n);
//        auto g = f;
//        f[0] = nums[0];
//        for (int i = 1; i < n; i++) {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(g[n - 1], f[n - 1]);
//    }
//};
//class Solution {
//public:
//    int calculateMinimumHP(vector<vector<int>>& dungeon) {
//        int m = dungeon.size(), n = dungeon[0].size();
//        vector<vector<int>>dp(m + 1, vector<int>(n + 1, INT_MAX));
//        dp[m][n - 1] = 1;
//        for (int i = m - 1; i >= 0; i--) {
//            for (int j = n - 1; j >= 0; j--) {
//                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
//                dp[i][j] = max(1, dp[i][j]);
//            }
//
//        }
//        return dp[0][0];
//    }
//};
//class Solution
//{
//public:
//    bool equationsPossible(vector<string>& equations)
//    {
//        vector<int> ufs(26, -1);
//        auto findRoot = [&ufs](int x)
//        {
//            while (ufs[x] >= 0)
//                x = ufs[x];
//
//            return x;
//        };
//        for (auto& str : equations) {
//            if (str[1] == '=') {
//                int root1 = findRoot(str[0] - 'a');
//                int root2 = findRoot(str[3] - 'a');
//                if (root1 != root2) {
//                    ufs[root1] += ufs[root2];
//                    ufs[root2] = root1;
//                }
//            }
//        }
//        for (auto& str : equations) {
//            if (str[1] == '!') {
//                int root1 = findRoot(str[0] - 'a');
//                int root2 = findRoot(str[3] - 'a');
//                if (root1 == root2) {
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
//};



//
//class UnionFindSet
//{
//public:
//    UnionFindSet(size_t n) : _ufs(n, -1) {}
//    void Union(int x1, int x2)
//    {
//        int p1 = FindRoot(x1);
//        int p2 = FindRoot(x2);
//        if (p1 == p2)
//            return;
//        if (p1 > p2)
//        {
//            swap(p1, p2);
//        }
//
//        _ufs[p1] += _ufs[p2];
//        _ufs[p2] = p1;
//    }
//    int FindRoot(int x)
//    {
//        int root = x;
//        while (_ufs[root] >= 0)
//        {
//            root = _ufs[root];
//        }
//        return root;
//    }
//    bool IsInSet(int x1, int x2)
//    {
//        int p1 = FindRoot(x1);
//        int p2 = FindRoot(x2);
//        return p1 == p2;
//    }
//    size_t SetSize()
//    {
//        size_t size = 0;
//        for (auto e : _ufs)
//        {
//            if (e < 0)
//                size++;
//        }
//        return size;
//    }
//
//private:
//    vector<int> _ufs;
//};
//class Solution {
//public:
//    int findCircleNum(vector<vector<int>>& isConnected) {
//        UnionFindSet ufs(isConnected.size());
//        for (size_t i = 0; i < isConnected.size(); i++) {
//            for (size_t j = 0; j < isConnected[0].size(); j++) {
//                if (isConnected[i][j] == 1)ufs.Union(i, j);
//            }
//        }
//        return ufs.SetSize();
//    }
//};

//class Solution {
//public:
//    bool isUnivalTree(TreeNode* root) {
//        if (root == NULL)return true;
//        if (root->left != NULL) {
//            if (root->left->val != root->val)return false;
//        }
//        if (root->right != NULL) {
//            if (root->right->val != root->val)return false;
//        }
//        return isUnivalTree(root->left) && isUnivalTree(root->right);
//    }
//};